// 01背包问题思路及算法实现 程序是一行一行的进行填表的。f
// [0][0, 1, 2, 3, 4.....]...... f[5][0, 1, 2, 3, 4....]  (
// 程序初始化的过程就是将第0行的所有数填为0，这是符合现实情况的。它表明当前背包没有装物品，当前背包的价值是0)2.拿f
// [3]
// [8] = 11来说明填表的过程。f[3] 表明i =
// 3(当前子问题有3个物品可选，分别是1，2，3号物品)，f
// [3]
// [*]
// 的值就是第3个子问题的解。我要选的3号物品的重量是6，它的价值是5，所以我会找到它的前6列的上一行所对应的背包的价值（f
// [2][2] ）
// + 5（当前要选的3号物品的价值） = 11,
// 值为11 > f[2][8] = 9，代表我选了1,
// 3的方案要优于选1，2的这种方案，所以我将11填入到表格【如果f[2][2] + 5 < 9,
// 则将9填入表格】-------------------这里需要说明一下f[2][8] =
// 9的含义：2子问题的一个解是 {
// 1，2} 选择1，2号物品所对应的背包价值为9。------恰巧我们在解决3子问题时{
// 1，2，3} 需要计算比较这几种方案，选1，2号物品{1，2} >>>>
// 背价 = ？，背包价格是多少，{1，3} >>>> 背价 = ？,
// {1，2, 3} >>>> 背价 =
// ？而{1, 2} >>
// 背包价格在2子问题中已给出，因此我们可以在3子问题中直接用。为何不考虑{
// 2，3}
// 呢？就是拿2号和3号组队放入背包？因为在2子问题中已经记载了：【如果要单选一个背包的话，选择1号获得的价值要比2号获得的价值大
// -- --我们追溯到f[2][2] = 6是整么来的，背包容量是2的时候，
// [1, 2] 号物品只能有一个放入背包，放入1，背包的价值是6，f[1][2] =
// 6的计算是在1子问题中已经求解出来的，2子问题可以直接用该值，而不用再重复计算。放入2号，背值是3，3
// < 6, 所以沿用上一个子问题的解作为该步的答案，所以f [2] [2]
// 是6，而不是3，所以它相当于定义说：下一个子问题在求解的过程中，如果遇到只能从2号和1号物品中选择一个物品装入背包时，请选择1号物品】
// 3.其实将上述的描述写成代码，就是两层for循环（遍历n，再嵌套遍历c），加上两个判断（1.当前子问题的可行的一个方案与上一个子问题的对应的可行方案谁最优。2.连续变量j的值是否达到了跳跃点的值，达到了才更新当前背包的价值）：代码如下
#include <stdio.h>

#include <iostream>
using namespace std;
void Knapsack(int n, int c, int *w, int *p) {
  int f[100][100];
  int i = 0, j = 0;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= c; j++) {
      f[i][j] = f[i - 1][j];
      if (j >= w[i]) {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + p[i]);
      }
    }
  }
  //因为我是i++和j++，循环结束，多加了一次i和j，所以最后要减回来
  cout << "背包能装的最大价值是：" << f[i - 1][j - 1] << endl;
}
int main() {
  int n;
  int c;

  /*
  int w[100];
  int p[100];
  cout << "请输入背包容量c："<< endl;
  cin >>c;
  cout <<"请输入物体个数n："<<endl;
  cin >>n;
  for(int i=1;i<=n;i++)
  {
  cout<<"请输入物重w["<<i<<"]："<<endl;
  cin >> w[i];
  }
  for(int i=1;i<=n;i++)
  {
  cout<<"请输入物价p["<<i<<"]："<<endl;
  cin >> p[i];
  }
  */
  c = 10;
  //背包容量c
  n = 5;
  //物体个数n
  int w[6] = {0, 2, 2, 6, 5, 4};
  //物重w
  int p[6] = {0, 6, 3, 5, 4, 6};
  //物价p
  Knapsack(n, c, w, p);
}